package br.ufmg.vod.wbr.algorithims.dfs;

import java.util.LinkedList;

import br.ufmg.vod.wbr.api.Graph;

public class IterativeDFS implements Runnable, DFS{
	
	public static byte WHITE = 0;
	public static byte GRAY = 1;
	public static byte BLACK = 2;
	
	private DFSData data;
	private LinkedList<DFSState> stack;

	public IterativeDFS(Graph g){
		this.stack = new LinkedList<DFSState>();
		this.data = new DFSData(g);
	}
	
	/* (non-Javadoc)
	 * @see br.ufmg.vod.wbr.algorithims.dfs.DFS#run()
	 */
	@Override
	public void run() {
		dfsAllVertex();

	}

	/* (non-Javadoc)
	 * @see br.ufmg.vod.wbr.algorithims.dfs.DFS#dfsAllVertex()
	 */
	public void dfsAllVertex() {
		for (int i = 0; i < this.data.graph.getNumVertex(); i++) {
			dfsSingleVertex(i);
		}
	}

	/* (non-Javadoc)
	 * @see br.ufmg.vod.wbr.algorithims.dfs.DFS#dfsSingleVertex(int)
	 */
	public void dfsSingleVertex(int i) {
		if( this.data.colors[i] == DFSData.WHITE){
			int startVertex = i;
			DFSState currentState = new DFSState(startVertex,-1);
			stack.addLast(currentState);
			this.data.colors[currentState.u] = GRAY;
			this.data.discoveryTime[currentState.u] = ++this.data.time;
			this.data.predecessor[currentState.u]=currentState.u;
			this.data.dist[currentState.u]=0;
			this.dfsVisit();
		}
	}

	
	private DFSData dfsVisit() {
		
		while(!stack.isEmpty()){
			recursion:{
				DFSState currentState = stack.removeLast();//recover state
				currentState.i++; //returns from recursion on last FOR line
				int[] neighbours = data.graph.getEdges(currentState.u); //recover neighbours var
				
				for (; currentState.i < neighbours.length; currentState.i++) {
					int v = neighbours[currentState.i];
					if( v < this.data.graph.getNumVertex() && this.data.colors[v] == WHITE  ){
						this.data.colors[v] = GRAY;
						this.data.discoveryTime[v] = ++this.data.time;
						this.data.predecessor[v]=currentState.u;
						this.data.dist[v]=this.data.dist[currentState.u]+1;
						stack.addLast(currentState); //RECURSION TIME XD!!!
						stack.addLast(new DFSState(v,-1));
						break recursion;
					}
				}
				
				this.data.colors[currentState.u] = BLACK;
				this.data.closeTime[currentState.u] = this.data.time;
//				this.data.stack.add(currentState.u);
				this.data.visitedStack.push(currentState.u);
			}

		}
		
		return this.data;
		
	}
	
	/* (non-Javadoc)
	 * @see br.ufmg.vod.wbr.algorithims.dfs.DFS#getData()
	 */
	public DFSData getData() {
		return data;
	}

	
	class DFSState{
		int u;
		int i;
		public DFSState(int u, int i) {
			this.u = u;
			this.i = i;
		}
	}


	@Override
	public void clear() {
		this.data.clearAllData();
	}
	




}
